package com.zdp.leetcodeMiddle;


/*
* 题目描述：
* 给你一个整数数组 nums，请你将该数组升序排列。
示例 1：
输入：nums = [5,2,3,1]
输出：[1,2,3,5]
示例 2：
输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]
提示：
1 <= nums.length <= 50000
-50000 <= nums[i] <= 50000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 排序数组_912 {

    /*
    * 解题思路：没什么好思路了 就是几个排序算法塞进去就完事了
    * https://leetcode-cn.com/problems/sort-an-array/solution/fu-xi-ji-chu-pai-xu-suan-fa-java-by-liweiwei1419/
    * */
    /*
    * 先来个快排
    * */
    public int[] sortArray(int[] nums) {
        quickSort(nums,0,nums.length-1);
        return nums;
    }

    public void quickSort(int[] nums,int left,int right){
        if(left<right){
            // 获取锚点
            int p = getPoint(nums,left,right);
            quickSort(nums,left,p-1);
            quickSort(nums,p+1,right);
        }
    }

    /*
    * i 指向 交换时的位置的前一位
    * j 指向 当前要交换的元素
    * */
    public int getPoint(int[] nums,int left,int right){
        int x = nums[right]; // 基准值
        int i = left -1;
        for(int j=left;j<right;j++){
            if(nums[j] <= x){
                swap(nums,++i,j);
            }
        }
        swap(nums,++i,right);
        return i;
    }

    public void swap(int[] nums,int x,int y){
        int temp = nums[x];
        nums[x] = nums[y];
        nums[y] = temp;
    }
}
